use std::collections::HashMap;
use std::fs::File;
use std::io::Read;
use serde_json;
#[derive(Debug)]
struct UnionFind {
    parent: HashMap<String, String>,
    rank: HashMap<String, u32>,
}

impl UnionFind {
    fn new(nodes : &Vec <String>) -> Self {
        let mut parent = HashMap::new();
        let mut rank = HashMap::new();

        for node in nodes {
            parent.insert(node.clone(),node.clone());
            rank.insert(node.clone(),0);
        }

        UnionFind { parent, rank }
    }

    fn find(&mut self, node: &String ) -> String{
        if self.parent.get(node).unwrap() != node {
            let parent = self.parent.get(node).unwrap().clone();
            let root = self.find(&parent);
            self.parent.insert(node.clone(), root.clone());
            return root;
        }
        else {
            return node.clone();
        }
    }

    fn union(&mut self, node1: &String, node2: &String){
        let root1 = self.find(node1);
        let root2 = self.find(node2);

        if root1!= root2 {
            let rank1 = self.rank.get(&root1).unwrap();
            let rank2 = self.rank.get(&root2).unwrap();

            if rank1 > rank2 {
                self.parent.insert(root2, root1);
            }else if rank1 < rank2 {
                self.parent.insert(root1, root2);
            }else{
                self.parent.insert(root2.clone(), root1.clone());
                self.rank.insert(root1,rank1+1);
            }
        }
    }

    fn connected_check(&mut self, node1: &String, node2: &String) -> bool{
        let root1 = self.find(node1);
        let root2 = self.find(node2);

        root1 == root2
    }
    
}
#[derive(Debug)]
struct Graph {
    nodes: HashMap<String, Vec<String>>, 
}

#[derive(Debug)]
struct MultiGraph {
    graphs: HashMap<usize, Graph>, 
}


impl MultiGraph {
    fn new_from_file(file_path: &str) -> Result<Self, String> {
        let mut file = File::open(file_path).map_err(|err| err.to_string())?;
        let mut content = String::new();
        file.read_to_string(&mut content).map_err(|err| err.to_string())?;
        
        let parsed: HashMap<String, HashMap<String, Vec<String>>> = 
            serde_json::from_str(&content).map_err(|err| err.to_string())?;
        let mut graphs = HashMap::new();

        for (key, value) in parsed {
            let graph_index = key.parse::<usize>().map_err(|e| e.to_string())?;
            let mut graph = Graph {
                nodes: HashMap::new(),
            };

            for (node, neighbors) in value {
                let entry = graph.nodes.entry(node).or_insert_with(Vec::new );
                entry.extend(neighbors);
            }

            graphs.insert(graph_index, graph);
        }

        Ok(MultiGraph { graphs })
    }
}

fn build_union_find(graph: &Graph) -> UnionFind {
    let nodes: Vec<String> = graph
        .nodes
        .keys()
        .chain(graph.nodes.values().flat_map(|v| v))
        .cloned()
        .collect();
    let mut uf = UnionFind::new(&nodes);

    for (node, neighbors) in &graph.nodes {
        for neighbor in neighbors {
            uf.union(node, neighbor);
        }
    }

    uf
}

pub fn count_provinces() -> String {
    let file_path = "district.json";
    
    let multi_graph = MultiGraph::new_from_file(file_path).unwrap();
    
    let mut res : Vec<(i32,i32)> = Vec::new();
    
    for (index, graph) in multi_graph.graphs.iter() {
        //println!("graph index: {},graph nodes:{:?} ", index, graph);
        let uf = build_union_find(graph);
        let mut count = 0;
        for node in uf.parent.keys() {
            if uf.parent.get(node).unwrap() == node {
                count += 1;
            }
        }
        res.push((*index as i32, count as i32));
    }
    
    res.sort_by_key(|&(key,_)| key);

    let mut res_str = String::new();
    for (index, count) in res {
        res_str += count.to_string().as_str();
        if index != (multi_graph.graphs.len())as i32 {
            res_str += ",";
        }
    }

    res_str
   
}
